package 哈夫曼编码;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;



public class 哈夫曼编码 {
	public static void main(String[] args) {
		//使用这个字符串，最后一个数组是0开头，后面解码会出错
		String content = "i like like like java do you like a java you are lihai";
//		String content = "i like like like java do youid";
//		String content = "i like like like java do you like a java";
		byte[] bytes = content.getBytes();
		System.out.println(bytes.length);
		
		//压缩
		HuffmanCode huffmanCode = new HuffmanCode();
		byte[] huffmanZip = huffmanCode.huffmanZip(bytes);
		System.out.println("压缩前："+content);
		System.out.println("压缩后："+Arrays.toString(huffmanZip));
		System.out.println(huffmanZip.length);
		System.out.println("压缩比："+(bytes.length-huffmanZip.length)*1000/bytes.length/1000.0);

		//哈夫曼编码表
		//System.out.println(huffmanCode.huffmanCodes);
		
		//解压
		//传入哈夫曼编码表和压缩后的哈夫曼编码
		byte[] newBytes = huffmanCode.decode(huffmanCode.huffmanCodes, huffmanZip);
		System.out.println("解压后："+new String(newBytes));
	}
}

/**
 * 哈夫曼编码
 * @author PC
 *
 */
class HuffmanCode {
	
	/**
	 * 第一步
	 * 把字节数组转成List
	 * @param bytes
	 * @return
	 */
	public List<Node> getNodes(byte[] bytes){
		
		//创建ArrayList
		ArrayList<Node> nodes = new ArrayList<Node>();
		
		//遍历bytes，统计每一个byte出现的次数 map[key,value]，结果Map{a:5,b:2,c:4}字节和次数
		Map<Byte,Integer> counts = new HashMap<Byte,Integer>();
		for(byte b : bytes) {
			//先去map中找找有没有统计过这个字符
			Integer count = counts.get(b);
			//空，如果没统计过，就加进去
			if(count == null) {
				counts.put(b,1);
			}else {
				//如果不为空，就把这个字符加一更新
				counts.put(b,count+1);
			}
		}
		
		//把每一个键值对转换成一个Node对象，并加入到nodes集合中
		//遍历，结果List{a:4,b:5,c:2}，注意Node构造顺序，字符：次数
		for(Map.Entry<Byte, Integer> entry : counts.entrySet()) {
			nodes.add(new Node(entry.getValue(),entry.getKey()));
		}
		return nodes;
	}
	
	/**
	 * 第二步
	 * 构造哈夫曼树，传入List
	 * @param nodes
	 * @return
	 */
	public Node huffmanTree(List<Node> nodes) {
		
		while(nodes.size()>1) {
			//排序
			Collections.sort(nodes);
			//取值
			Node leftNode = nodes.get(0);
			Node rightNode = nodes.get(1);
			//新节点，非叶子结点没有值，只有权重
			Node parentNode = new Node(leftNode.weight+rightNode.weight, null);
			parentNode.left = leftNode;
			parentNode.right = rightNode;
			//移除、添加
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			nodes.add(parentNode);
		}
		//只剩下一个根节点
		return nodes.get(0);
	}
	
	
	//第三步
	//1. 将赫夫曼编码表存放在 Map<Byte,String> 形式 生成的赫夫曼编码表{32=01, 97=100, 100=11000, ...
	static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();
	//2. 在生成赫夫曼编码表示，需要去拼接路径, 定义一个StringBuilder 存储某个叶子结点的路径
	static StringBuilder stringBuilder = new StringBuilder();
	
	/**
	 * 生成哈夫曼树对应的哈夫曼编码，是每一个字符对应的编码
	 * @param node 传入结点
	 * @param code 路径，走左子结点为0，走右子结点为1
	 * @param stringBuilder 用于拼接路径
	 */
	public void getHuffManCode(Node node, String code, StringBuilder stringBuilder) {
		
		StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
		
		//将code路径加入stringBuilder2
		stringBuilder2.append(code);
		
		//不为空，判断结点走左边还是右边
		if(node != null) {
			//data空，说明是非叶子节点，因为在构建树时，新生成的非叶子结点没有data，只有权重
			if(node.data == null) {
				//递归
				getHuffManCode(node.left, "0", stringBuilder2);
				getHuffManCode(node.right, "1", stringBuilder2);
			}else {
				//叶子结点，就把data和整个路径放入map，因为只有叶子结点才是原始的byte
				huffmanCodes.put(node.data,stringBuilder2.toString());
			}
		}
	}
	
	/**
	 *  重载，返回哈夫曼编码
	 * @param root
	 * @return
	 */
	public Map<Byte,String> getHuffManCode(Node root){
		if(root == null) {
			return null;
		}else {
			//有坑！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
			//下面这三种，第一个是错的，因为StringBuild会把null加进去，要用""，下面两个是老师的写法
			//可以简写
			//getHuffManCode(root, null, stringBuilder);
			//getHuffManCode(root.left, "0", stringBuilder);
			//getHuffManCode(root.right, "1", stringBuilder);
			getHuffManCode(root, "", stringBuilder);
		}
		
//		for(Map.Entry<Byte, String> map : huffmanCodes.entrySet()) {
//			System.out.println(map.getKey()+"---"+map.getValue());
//		}
		return huffmanCodes;
	}
	
	//声明一个变量，记录数组最后一位开头有几个0
	static int zeroCount = 0;
	
	/**
	 * 第四步
	 * 把哈夫曼编码压缩后的数组，8位一组，是原始数组对应的编码
	 * @param bytes 原始byte数组
	 * @param huffmanCodes 哈夫曼编码
	 * @return
	 */
	public byte[] zip(byte[] bytes, Map<Byte,String> huffmanCodes) {
		//利用哈夫曼编码把原始字节数组，转成指定哈夫曼编码
		StringBuilder stringBuilder = new StringBuilder();
		for(byte b : bytes) {
			//结果就是原始数组的哈夫曼编码：1001010110101110100...
			stringBuilder.append(huffmanCodes.get(b));
		}
		
		//哈夫曼编码
		//System.out.println(stringBuilder);
		
		//求出byte[] huffmanCode的数组长度
		//简单办法：len = (stringBuilder.length() + 7) / 8；这样无论是否倍数都可以求出 
//		int len = (stringBuilder.length() + 7) / 8;
		int len;
		if(stringBuilder.length() % 8 == 0) {
			len = stringBuilder.length() / 8;
		}else {
			len = stringBuilder.length() / 8 + 1;
		}
		
		//创建数组
		byte[] huffmanCodeBytes = new byte[len];
		//记录第几个byte
		int index = 0;
		
		//每次取8个
		for(int i = 0; i < stringBuilder.length(); i += 8) {
			String str;
			//不够8位，直接取完，最后一个很可能不是8位，在解压时注意
			if(i+8>stringBuilder.length()) {
				str = stringBuilder.substring(i);
				//--------------注意-------------------
				//如果最后几位不满8位，且为0开头，如0010这种情况，在后面会转成(int)2，
				//这样的话，在解码时，2转成二进制为10，就和0010编码对不上了，此处需要记录开头有几个零
				
				//如果最后一次是00110010、0110等情况，需要记录前面有多少个0
				for(int j = 0; j < str.length(); j++) {
					//这三行暂定
//					if(str.length() == 1) {
//						break;
//					}
					if(str.charAt(j) == '0') {
						zeroCount++;
					}else {
						break;
					}
				}
			}else {
				str = stringBuilder.substring(i,i + 8);
				
			}
			//将取出的8个放入数组中，二进制转十进制，转byte，最后一个可能是0开头
			System.out.println(str);
			huffmanCodeBytes[index] = (byte) Integer.parseInt(str, 2);
			index++;
		}
		//返回处理好的数组
		return huffmanCodeBytes;
	}
	
	
	//封装
	/**
	 * 第五步
	 * @param bytes
	 * @return
	 */
	public byte[] huffmanZip(byte[] bytes) {
		//数组转集合
		List<Node> nodes = getNodes(bytes);
		//集合创建哈夫曼树
		Node huffmanTree = huffmanTree(nodes);
		//哈夫曼树对应哈夫曼编码
		Map<Byte, String> huffManCode = getHuffManCode(huffmanTree);
		//根据哈夫曼编码的到指定压缩后哈夫曼数组
		byte[] zip = zip(bytes, huffManCode);
		return zip;
	}
	
	/****************************解压******************************/
	/**
	 * 将字节数组转二进制，用了补码的概念
	 * @param flag
	 * @param b
	 * @return
	 */
	public String byteToBitStr(boolean flag, Byte b) {
		
		//使用变量保存b，注意是int类型
		int temp = b;
		//使用按位或，补高位，在最后一位正数时，补高位会造成长度边长，所以最后一位不要补
		//如果是负数就是8位，若正数，则有多长就取多长
		if(flag) {
			temp |= 256;
		}
		//转二进制
		String str = Integer.toBinaryString(temp);
		//如果不是最后一位，直接取
		if(flag) {
			return str.substring(str.length()-8);
		}
		//-------------------解码时，在10前面补0，变成0010---------------
		for(int i = 0; i < zeroCount; i++) {
			//最后一位按照解码时，补0
			str = "0" + str;
		}
		return str;
	}
	
	/**
	 * 传入哈夫曼编码表，和压缩编码
	 * @param huffmanCode
	 * @param bytes
	 * @return
	 */
	public byte[] decode(Map<Byte,String> huffmanCode, byte[] bytes) {
		//先得到数组对应的二进制码
		StringBuilder sb = new StringBuilder();
		for(int i = 0 ; i < bytes.length ; i++) {
			byte b = bytes[i];
			//是否最后一位
			boolean flag = ( i == bytes.length-1);
			//一直false，除了最后一位不压缩，其他都压缩
			sb.append(byteToBitStr(!flag, b));
		}
		
		System.out.println(sb);
		
		//调换哈夫曼编码表
		Map<String,Byte> map = new HashMap<>();
		for(Map.Entry<Byte, String> huffman : huffmanCode.entrySet()) {
			map.put(huffman.getValue(), huffman.getKey());
		}
		
		//从二进制表利用编码表找出原始字节，放入List
		List<Byte> list = new ArrayList<>();
		//遍历，扫描，注意i的增量
		for(int i = 0 ; i < sb.length() ; ) {
			
			//计数器，每次扫描多长
			int count = 1;
			//是否找到
			boolean flag = true;
			//存放
			Byte b = null;
			
			//一直找
			while(flag) {
				//i不动，每次count向后移动找，每次找一个就比对一下
				String key = sb.substring(i, i+count);
				b = map.get(key);
				
				if(b == null) {
					count++;
				}else {
					flag = false;
				}
			}
			//找到放入lsit
			list.add(b);
			//i移动到下一个位置开始找
			i = i+count;
		}
		
		//找到所有字符，放到一起
		byte b[] = new byte[list.size()];
		for(int i = 0 ; i < b.length ; i++) {
			b[i] = list.get(i);
		}
		return b;
		
	}
}

/**
 * 结点，有权重和值
 * @author PC
 *
 */
class Node implements Comparable<Node> {
	
	//权重
	public int weight;
	//值
	public Byte data;
	public Node left;
	public Node right;
	//构造器
	public Node(int weight, Byte data) {
		super();
		this.weight = weight;
		this.data = data;
	}
	@Override
	public String toString() {
		return "Node [weight=" + weight + ", data=" + data + "]";
	}
	//比较器规则
	@Override
	public int compareTo(Node o) {
		// 从小到大
		return this.weight - o.weight;
	}
	
	
}